package demo2;

import javax.print.attribute.standard.PrinterResolution;
import java.util.Arrays;

public class Sort {

    //快速排序
    public void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        //寻找基准
        int point = findPoint(arr, left, right);
        quick(arr, left, point - 1);
        quick(arr, point + 1, right);
    }

    private int findPoint(int[] arr, int left, int right) {
        int key = arr[left];
        while (left < right) {
            while(left < right && arr[right] >= key) {
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= key) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }

}

class Main {
    public static void main(String[] args) {
        int[] arr = {3,1,4,2,6,7,5,9,8};
        Sort sort = new Sort();
        sort.quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}